{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sentence Similarity II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #array #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #数组 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: areSentencesSimilarTwo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #句子相似性 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>我们可以将一个句子表示为一个单词数组，例如，句子 <code>I am happy with leetcode\"</code>可以表示为&nbsp;<code>arr = [\"I\",\"am\",happy\",\"with\",\"leetcode\"]</code></p>\n",
    "\n",
    "<p>给定两个句子 <code>sentence1</code> 和 <code>sentence2</code> 分别表示为一个字符串数组，并给定一个字符串对 <code>similarPairs</code> ，其中&nbsp;<code>similarPairs[i] = [x<sub>i</sub>, y<sub>i</sub>]</code>&nbsp;表示两个单词&nbsp;<code>x<sub>i</sub></code>&nbsp;和&nbsp;<code>y<sub>i</sub></code>&nbsp;是相似的。</p>\n",
    "\n",
    "<p>如果 <code>sentence1</code> 和 <code>sentence2</code> 相似则返回 <code>true</code> ，如果不相似则返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>两个句子是相似的，如果:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>它们具有 <strong>相同的长度</strong> (即相同的字数)</li>\n",
    "\t<li><code>sentence1[i]</code>&nbsp;和&nbsp;<code>sentence2[i]</code>&nbsp;是相似的</li>\n",
    "</ul>\n",
    "\n",
    "<p>请注意，一个词总是与它自己相似，也请注意，相似关系是可传递的。例如，如果单词 <code>a</code> 和 <code>b</code> 是相似的，单词&nbsp;<code>b</code> 和 <code>c</code> 也是相似的，那么 <code>a</code> 和 <code>c</code> 也是 <strong>相似</strong> 的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> sentence1 = [\"great\",\"acting\",\"skills\"], sentence2 = [\"fine\",\"drama\",\"talent\"], similarPairs = [[\"great\",\"good\"],[\"fine\",\"good\"],[\"drama\",\"acting\"],[\"skills\",\"talent\"]]\n",
    "<strong>输出:</strong> true\n",
    "<strong>解释:</strong> 这两个句子长度相同，每个单词都相似。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> sentence1 = [\"I\",\"love\",\"leetcode\"], sentence2 = [\"I\",\"love\",\"onepiece\"], similarPairs = [[\"manga\",\"onepiece\"],[\"platform\",\"anime\"],[\"leetcode\",\"platform\"],[\"anime\",\"manga\"]]\n",
    "<strong>输出:</strong> true\n",
    "<strong>解释:</strong> \"leetcode\" --&gt; \"platform\" --&gt; \"anime\" --&gt; \"manga\" --&gt; \"onepiece\".\n",
    "因为“leetcode”和“onepiece”相似，而且前两个单词是相同的，所以这两句话是相似的。</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> sentence1 = [\"I\",\"love\",\"leetcode\"], sentence2 = [\"I\",\"love\",\"onepiece\"], similarPairs = [[\"manga\",\"hunterXhunter\"],[\"platform\",\"anime\"],[\"leetcode\",\"platform\"],[\"anime\",\"manga\"]]\n",
    "<strong>输出:</strong> false\n",
    "<strong>解释: </strong>“leetcode”和“onepiece”不相似。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= sentence1.length, sentence2.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= sentence1[i].length, sentence2[i].length &lt;= 20</code></li>\n",
    "\t<li><code>sentence1[i]</code>&nbsp;和&nbsp;<code>sentence2[i]</code>&nbsp;只包含大小写英文字母</li>\n",
    "\t<li><code>0 &lt;= similarPairs.length &lt;= 2000</code></li>\n",
    "\t<li><code>similarPairs[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= x<sub>i</sub>.length, y<sub>i</sub>.length &lt;= 20</code></li>\n",
    "\t<li><code>x<sub>i</sub></code>&nbsp;和&nbsp;<code>y<sub>i</sub></code>&nbsp;只含英文字母</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sentence-similarity-ii](https://leetcode.cn/problems/sentence-similarity-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sentence-similarity-ii](https://leetcode.cn/problems/sentence-similarity-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"great\",\"acting\",\"skills\"]\\n[\"fine\",\"drama\",\"talent\"]\\n[[\"great\",\"good\"],[\"fine\",\"good\"],[\"drama\",\"acting\"],[\"skills\",\"talent\"]]', '[\"I\",\"love\",\"leetcode\"]\\n[\"I\",\"love\",\"onepiece\"]\\n[[\"manga\",\"onepiece\"],[\"platform\",\"anime\"],[\"leetcode\",\"platform\"],[\"anime\",\"manga\"]]', '[\"I\",\"love\",\"leetcode\"]\\n[\"I\",\"love\",\"onepiece\"]\\n[[\"manga\",\"hunterXhunter\"],[\"platform\",\"anime\"],[\"leetcode\",\"platform\"],[\"anime\",\"manga\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        #一眼并查集\n",
    "        if len(sentence1)!=len(sentence2):\n",
    "            return False\n",
    "        parent={}\n",
    "        for a,b in similarPairs:\n",
    "            parent[a]=a\n",
    "            parent[b]=b\n",
    "        for i in range(len(sentence1)):\n",
    "            parent[sentence1[i]]=sentence1[i]\n",
    "            parent[sentence2[i]]=sentence2[i]\n",
    "        def find(i):\n",
    "            if parent[i]==i:\n",
    "                return i\n",
    "            else:\n",
    "                parent[i]=find(parent[i])\n",
    "                return parent[i]\n",
    "        def union(i,j):\n",
    "            x,y=find(i),find(j)\n",
    "            parent[x]=y\n",
    "        for i,j in similarPairs:\n",
    "            union(i,j)\n",
    "        for i in range(len(sentence2)):\n",
    "            x,y=sentence1[i],sentence2[i]\n",
    "            if find(x)!=find(y):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, x) -> None:\n",
    "        self.uf = [-1] * x\n",
    "\n",
    "    def find(self, x):\n",
    "        r = x\n",
    "        while self.uf[x] >= 0:\n",
    "            x = self.uf[x]\n",
    "\n",
    "        while r != x:\n",
    "            self.uf[r], r = x, self.uf[r]\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        ux, uy = self.find(x), self.find(y)\n",
    "        if ux == uy:\n",
    "            return\n",
    "        if self.uf[ux] >= self.uf[uy]:\n",
    "            self.uf[uy] += self.uf[ux]\n",
    "            self.uf[ux] = uy\n",
    "        else:\n",
    "            self.uf[ux] += self.uf[uy]\n",
    "            self.uf[uy] = ux\n",
    "        return\n",
    "\n",
    "    def count(self):\n",
    "        ans = 0\n",
    "        for c in self.uf:\n",
    "            if c < 0 and c != -1:\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "    def valid(self):\n",
    "        n = len(self.uf)\n",
    "        for c in range(n):\n",
    "            if self.uf[c] == -n:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def __print__(self):\n",
    "        return self.uf\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        m = {}\n",
    "        v = set()\n",
    "        for s in sentence1 + sentence2:\n",
    "            v.add(s)\n",
    "        for s1,s2 in similarPairs:\n",
    "            v.add(s1)\n",
    "            v.add(s2)\n",
    "        v = list(v)\n",
    "        cur = 0\n",
    "        rm = {}\n",
    "        uf = UnionFind(len(v))\n",
    "        for i in range(len(v)):\n",
    "            m[i] = v[i]\n",
    "            rm[v[i]] = i\n",
    "        for s1,s2 in similarPairs:\n",
    "            uf.union(rm[s1],rm[s2])\n",
    "        for i in range(len(sentence1)):\n",
    "            s1,s2 = sentence1[i],sentence2[i]\n",
    "            if s1 not in rm or s2 not in rm:\n",
    "                if s1 != s2:\n",
    "                    return False\n",
    "            r1,r2 = uf.find(rm[s1]),uf.find(rm[s2])\n",
    "            if r1 != r2:\n",
    "                return False\n",
    "        return True\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        fa=dict()\n",
    "        def find(x):\n",
    "            #print(x)\n",
    "            if x not in fa:\n",
    "                fa[x]=x\n",
    "            if fa[x]!=x:\n",
    "                fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(a,b):\n",
    "            if find(a)!=find(b):\n",
    "                fa[find(a)]=find(b)\n",
    "        for a,b in similarPairs:\n",
    "            union(a,b)\n",
    "        n=len(sentence1)\n",
    "        if len(sentence2)!=n:\n",
    "            return False \n",
    "        for i in range(n):\n",
    "            if find(sentence1[i])!=find(sentence2[i]):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        _set = set()  \n",
    "        for x in sentence1 + sentence2:\n",
    "            _set.add(x)\n",
    "        for x,y in similarPairs:\n",
    "            _set.add(x)\n",
    "            _set.add(y)\n",
    "        \n",
    "        arr = list(_set) \n",
    "        n = len(arr)\n",
    "        fa = list(range(n))\n",
    "\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        \n",
    "        def union(x,y):\n",
    "            fa[find(x)] = find(y)\n",
    "        \n",
    "        def same(x,y):\n",
    "            return find(x) == find(y)\n",
    "\n",
    "        d = {x:i for i,x in enumerate(arr)}\n",
    "        \n",
    "        for x,y in similarPairs:\n",
    "            union(d[x], d[y])\n",
    "\n",
    "        for x,y in zip(sentence1,sentence2):\n",
    "            if x != y and not same(d[x],d[y]):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "'''\n",
    "--- 从此处复制 ---\n",
    "'''\n",
    "class IdentityDefaultDict(defaultdict):\n",
    "    '''\n",
    "    该类用于处理并查集初始化的恒等映射\n",
    "    '''\n",
    "    def __missing__(self, key):\n",
    "        return key\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n=None):\n",
    "        self.parent = IdentityDefaultDict()\n",
    "        if n: self.parent = list(range(n))\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x: self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    def merge(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x != y: self.parent[x] = y\n",
    "    def count_groups(self):\n",
    "        return len(set(self.find(x) for x in self.parent))\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        uf = UnionFind()\n",
    "        for x, y in similarPairs:\n",
    "            uf.merge(x, y)\n",
    "        if len(sentence1) != len(sentence2): return False\n",
    "        for x, y in zip(sentence1, sentence2):\n",
    "            if uf.find(x) != uf.find(y): return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        #一眼并查集\n",
    "        if len(sentence1)!=len(sentence2):\n",
    "            return False\n",
    "        parent={}\n",
    "        for a,b in similarPairs:\n",
    "            parent[a]=a\n",
    "            parent[b]=b\n",
    "        for i in range(len(sentence1)):\n",
    "            parent[sentence1[i]]=sentence1[i]\n",
    "            parent[sentence2[i]]=sentence2[i]\n",
    "        def find(i):\n",
    "            if parent[i]==i:\n",
    "                return i\n",
    "            else:\n",
    "                parent[i]=find(parent[i])\n",
    "                return parent[i]\n",
    "        def union(i,j):\n",
    "            x,y=find(i),find(j)\n",
    "            parent[x]=y\n",
    "        for i,j in similarPairs:\n",
    "            union(i,j)\n",
    "        for i in range(len(sentence2)):\n",
    "            x,y=sentence1[i],sentence2[i]\n",
    "            if find(x)!=find(y):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.father = {}\n",
    "    def add(self, x: str):\n",
    "        if x not in self.father:\n",
    "            self.father[x] = None\n",
    "        \n",
    "    def merge(self, x: str, y: str):\n",
    "        root_x, root_y = self.find(x), self.find(y)\n",
    "        if root_x != root_y:\n",
    "            self.father[root_x] = root_y\n",
    "    def find(self, x: str):\n",
    "        root = x\n",
    "        while self.father[root] != None:\n",
    "            root = self.father[root]\n",
    "        while root != x:\n",
    "            original_father = self.father[x]\n",
    "            self.father[x] = root\n",
    "            x = original_father\n",
    "        return root\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        uf = UnionFind()\n",
    "        for word1, word2 in similarPairs:\n",
    "            uf.add(word1)\n",
    "            uf.add(word2)\n",
    "            uf.merge(word1, word2)\n",
    "        for i in range(len(sentence1)):\n",
    "            w1, w2 = sentence1[i], sentence2[i]\n",
    "            if w1 == w2 or (w1 in uf.father and w2 in uf.father and uf.find(sentence1[i]) == uf.find(sentence2[i])):\n",
    "                continue\n",
    "            return False\n",
    "        return True \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    sentences are similar:\n",
    "    1. same length\n",
    "    2. the word in the same position had the same final root\n",
    "    '''\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2) or not similarPairs:\n",
    "            return False \n",
    "\n",
    "        n = len(similarPairs)\n",
    "        id = defaultdict(str)\n",
    "\n",
    "        for pair in similarPairs: # find all words relationship\n",
    "            if pair[0] not in id:\n",
    "                id[pair[0]] = pair[0]\n",
    "            if pair[1] not in id:\n",
    "                id[pair[1]] = pair[1]\n",
    "            p = self.find_root(id, pair[0])  \n",
    "            q = self.find_root(id, pair[1])\n",
    "            id[q] = p \n",
    "\n",
    "        for i in id:\n",
    "            id[i] = self.find_root(id, i)\n",
    "        \n",
    "        for i in range(len(sentence1)): # go over every position\n",
    "            if id[sentence1[i]] == id[sentence2[i]] or id[sentence2[i]] == id[sentence1[i]]:\n",
    "                continue\n",
    "            else:\n",
    "                return False \n",
    "        return True\n",
    "\n",
    "    def find_root(self, id, i):\n",
    "        while i != id[i]:\n",
    "            id[i] = id[id[i]]\n",
    "            i = id[i]\n",
    "        return i "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        \n",
    "        p=collections.defaultdict()\n",
    "        \n",
    "        if len(sentence1)!=len(sentence2):\n",
    "            return False\n",
    "        \n",
    "        n=len(sentence1)\n",
    "        for a,b in zip(sentence1,sentence2):\n",
    "            p[a]=a\n",
    "            p[b]=b\n",
    "        \n",
    "        def find(x):\n",
    "            if p[x]==x:\n",
    "                return p[x]\n",
    "            p[x]=find(p[x])\n",
    "            return p[x]\n",
    "        def union(x,y):\n",
    "            p[find(x)]=find(y)\n",
    "        \n",
    "        for x,y in similarPairs:\n",
    "            if x not in p:\n",
    "                p[x]=x \n",
    "            if y not in p :\n",
    "                p[y]=y\n",
    "            union(x,y)\n",
    "        \n",
    "        for a,b in zip(sentence1,sentence2):\n",
    "            if find(a)!=find(b):\n",
    "                return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.part = n\n",
    "        self.parent = [x for x in range(n)]\n",
    "        self.size = [1 for x in range(n)]\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x, root_y = self.find(x), self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] > self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.parent[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_part_size(self, x):\n",
    "        root_x = self.find(x)\n",
    "        return self.size[root_x]\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2): return False\n",
    "\n",
    "        words = set(sentence1).union(set(sentence2))\n",
    "        for word1, word2 in similarPairs:\n",
    "            words.add(word1)\n",
    "            words.add(word2)\n",
    "        words = list(words)\n",
    "        words_dict = {word: i for i, word in enumerate(words)}\n",
    "\n",
    "        uf = UnionFind(len(words))\n",
    "        for word1, word2 in similarPairs:\n",
    "            uf.union(words_dict[word1], words_dict[word2])\n",
    "        \n",
    "        for i in range(len(sentence1)):\n",
    "            if not uf.is_connected(words_dict[sentence1[i]], words_dict[sentence2[i]]):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        m, n = len(sentence1), len(sentence2)\n",
    "        if m != n: return False\n",
    "        q = len(similarPairs)\n",
    "        g = defaultdict(list)\n",
    "        for x, y in similarPairs:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        for x, y in zip(sentence1, sentence2):\n",
    "            if x == y: continue\n",
    "            st = [x]\n",
    "            vis = set()\n",
    "            vis.add(x)\n",
    "            while st:\n",
    "                cur = st.pop()\n",
    "                if cur == y: break\n",
    "                for z in g[cur]:\n",
    "                    if z not in vis:\n",
    "                        vis.add(z)\n",
    "                        st.append(z)\n",
    "            else:\n",
    "                return False\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        p = defaultdict(str) \n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False \n",
    "        def find(x):\n",
    "            if x not in p:\n",
    "                p[x] = x \n",
    "                return x \n",
    "            if x == p[x]:\n",
    "                return x \n",
    "            p[x] = find(p[x]) \n",
    "            return p[x] \n",
    "        def un(x, y):\n",
    "            fx,fy = find(x), find(y)\n",
    "            if fx == fy:\n",
    "                return False \n",
    "            else:\n",
    "                p[fy] = fx \n",
    "                return True \n",
    "        def same(x,y):\n",
    "            fx,fy = find(x), find(y)\n",
    "            return fx == fy\n",
    "\n",
    "        for a, b in similarPairs:\n",
    "            un(a,b)\n",
    "\n",
    "        for a, b in zip(sentence1, sentence2):\n",
    "            if not same(a,b):\n",
    "                return False \n",
    "        return True \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        parents = {}\n",
    "        for x, y in similarPairs:\n",
    "            parents[x] = x\n",
    "            parents[y] = y\n",
    "        def find(index):\n",
    "            if parents[index] != index:\n",
    "                return find(parents[index])\n",
    "            return parents[index]\n",
    "        def union(index1, index2):\n",
    "            parents[find(index1)] = find(index2)\n",
    "        for x, y in similarPairs:\n",
    "            union(x, y)\n",
    "        for x, y in zip(sentence1, sentence2):\n",
    "            if (x == y) or (x in parents and y in parents and find(x) == find(y)):\n",
    "                continue\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 思路的心得：\n",
    "# 本质 无向图 两点间的连通性\n",
    "# 能给每个对象（结点）赋唯一ID号。则无脑并查集\n",
    "\n",
    "class UnionFind:        #### 手写并查集\n",
    "    def __init__(self, n):\n",
    "        self.parent = [x for x in range(n)]     #直系师傅，父指针\n",
    "        self.size = [1 for _ in range(n)]       #某个人手下的人数\n",
    "        self.part = n                           #江湖上门派的个数==图中连通域的个数\n",
    "    \n",
    "    def Find(self, x: int) -> int:  #寻找掌门\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        return self.Find(self.parent[x])\n",
    "    \n",
    "    def Union(self, x: int, y: int) -> bool:    #两个人合并为一个门派\n",
    "        root_x = self.Find(x)\n",
    "        root_y = self.Find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] > self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.parent[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        return True\n",
    "    \n",
    "    def connected(self, x: int, y: int) -> bool:    #判断两人是否在同一门派\n",
    "        return self.Find(x) == self.Find(y)\n",
    "    \n",
    "    def get_part_size(self, x: int) -> int:         #所在门派的人数\n",
    "        root_x = self.Find(x)\n",
    "        return self.size[root_x]\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, words1: List[str], words2: List[str], pairs: List[List[str]]) -> bool:\n",
    "        if len(words1) != len(words2):      #长度不同，必不相似\n",
    "            return False\n",
    "        n = len(words1)\n",
    "        UF = UnionFind(2 * len(pairs))      #并查集\n",
    "        word_ID = defaultdict(int)          #单词和它的唯一ID号\n",
    "        ID = 0\n",
    "        for pair in pairs:\n",
    "            for w in pair:\n",
    "                if w not in word_ID:\n",
    "                    word_ID[w] = ID\n",
    "                    ID += 1\n",
    "            UF.Union(word_ID[pair[0]], word_ID[pair[1]])    #每一对都是连通的（无向图中）\n",
    "        \n",
    "        for w1, w2 in zip(words1, words2):\n",
    "            if w1 == w2:        #同一个单词，必然相似\n",
    "                continue\n",
    "            else:\n",
    "                if w1 in word_ID and w2 in word_ID: #在pairs中出现过\n",
    "                    if UF.connected(word_ID[w1], word_ID[w2]) == True:  #相似==无向图中连通==两人在同一个门派\n",
    "                        continue\n",
    "                    else:\n",
    "                        return False\n",
    "                else:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(\n",
    "        self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]\n",
    "    ) -> bool:\n",
    "        m, n = len(sentence1), len(sentence2)\n",
    "        if m != n:\n",
    "            return False\n",
    "        root = {}\n",
    "\n",
    "        def find(i):\n",
    "            if i not in root:\n",
    "                root[i] = i\n",
    "            elif root[i] != i:\n",
    "                root[i] = find(root[i])\n",
    "            return root[i]\n",
    "\n",
    "        def union(i, j):\n",
    "            ri, rj = find(i), find(j)\n",
    "            if ri != rj:\n",
    "                root[rj] = ri\n",
    "\n",
    "        for i, j in similarPairs:\n",
    "            union(i, j)\n",
    "        for i in range(n):\n",
    "            if find(sentence2[i]) != find(sentence1[i]):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.size = [1]*n\n",
    "        self.part = n\n",
    "\n",
    "    def find(self, x):\n",
    "        if x != self.root[x]:\n",
    "            # 在查询的时候合并到顺带直接根节点\n",
    "            root_x = self.find(self.root[x])\n",
    "            self.root[x] = root_x\n",
    "            return root_x\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return\n",
    "        if self.size[root_x] >= self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        # 将非根节点的秩赋0\n",
    "        self.size[root_x] = 0\n",
    "        self.part -= 1\n",
    "        return\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_root_part(self):\n",
    "        # 获取每个根节点对应的组\n",
    "        part = defaultdict(list)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "\n",
    "    def get_root_size(self):\n",
    "        # 获取每个根节点对应的组大小\n",
    "        size = defaultdict(int)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            size[self.find(i)] = self.size[self.find(i)]\n",
    "        return size\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        m, n = len(sentence1), len(sentence2)\n",
    "        if m != n: return False\n",
    "        \n",
    "        words = set(sentence1).union(set(sentence2))\n",
    "        for word1, word2 in similarPairs:\n",
    "            words.add(word1)\n",
    "            words.add(word2)\n",
    "        \n",
    "        words = list(words)\n",
    "        dic = {word: i for i, word in enumerate(words)}\n",
    "        uf = UnionFind(len(words))\n",
    "\n",
    "        for word1, word2 in similarPairs:\n",
    "            uf.union(dic[word1], dic[word2])\n",
    "        \n",
    "        for i in range(m):\n",
    "            if not uf.is_connected(dic[sentence1[i]], dic[sentence2[i]]):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.part = n\n",
    "        self.parent = [x for x in range(n)]\n",
    "        self.size = [1 for x in range(n)]\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x, root_y = self.find(x), self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] > self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.parent[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_part_size(self, x):\n",
    "        root_x = self.find(x)\n",
    "        return self.size[root_x]\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2): return False\n",
    "\n",
    "        words = set(sentence1).union(set(sentence2))\n",
    "        for word1, word2 in similarPairs:\n",
    "            words.add(word1)\n",
    "            words.add(word2)\n",
    "        words = list(words)\n",
    "        words_dict = {word: i for i, word in enumerate(words)}\n",
    "\n",
    "        uf = UnionFind(len(words))\n",
    "        for word1, word2 in similarPairs:\n",
    "            uf.union(words_dict[word1], words_dict[word2])\n",
    "        \n",
    "        for i in range(len(sentence1)):\n",
    "            if not uf.is_connected(words_dict[sentence1[i]], words_dict[sentence2[i]]):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        def bfs(src, id) -> None:\n",
    "            q = deque([src])\n",
    "            seen.add(src)\n",
    "            while q:\n",
    "                cur = q.popleft()\n",
    "                word_id[cur] = id\n",
    "                for nxt in graph[cur]:\n",
    "                    if nxt not in seen:\n",
    "                        q.append(nxt)\n",
    "                        seen.add(nxt)\n",
    "        \n",
    "        if len(sentence1) != len(sentence2):  # edge case\n",
    "            return False\n",
    "        graph = defaultdict(set)\n",
    "        for u, v in similarPairs:  # build graph\n",
    "            graph[u].add(v)\n",
    "            graph[v].add(u)\n",
    "        # BFS\n",
    "        seen = set()\n",
    "        word_id = {}  # word -> id\n",
    "        id = 0\n",
    "        for word in graph.keys():  # mark components\n",
    "            if word not in seen:\n",
    "                bfs(word, id)\n",
    "                id += 1\n",
    "        return all(w1 == w2 or (w1 in word_id and w2 in word_id and word_id[w1] == word_id[w2]) for w1, w2 in\n",
    "                   zip(sentence1, sentence2))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
